/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package BuildGrid;

import static Edge.BuildEdge.All_Vertex;
import static Edge.BuildEdge.column;
import static Edge.BuildEdge.dvalue;
import static Edge.BuildEdge.grids;
import static Edge.BuildEdge.row;
import static Edge.BuildEdge.width;
import Graph.Car;
import Graph.Vertex;
import Graph.Vnode;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;

/**
 *
 * @author 江南才俊周涛涛
 */
public class Search {

    private int query_name;//查询点
    public static int k =1 ;//总共有k辆车
    private int k_now = 0;//现在找到k_now辆车
    private int x;//查询点所在的格子
    private int y;
    private int level = 0;//扩展层数
    private List<Car> cars = new ArrayList<Car>();
    private HashSet<Integer> current_names = new HashSet<Integer>(800);
    private HashSet<Integer> remove_names = new HashSet<Integer>(800);
    private double mini_border;//离查询点最近一个边界点的距离
    Integer min_pos;
    double min_value = Double.MAX_VALUE;
    double max_car = Double.MIN_VALUE;//k辆车中离query最远的车的距离
    Vertex qv;//查询点
    long sum_car = 0;
    double m, n, p, q;
    public long sumtime=0;

    public Search(int query_name, int i, int j) {

        System.out.println("i=" + i + "    j=" + j);
        current_names.clear();
        qv = All_Vertex.get(query_name);
        cars.addAll(qv.cars);
        if (cars.size() != 0) {
            max_car = cars.get(cars.size() - 1).query_dis;
        }
        mini_border = qv.max_dis;
        if (cars.size() > k && cars.get(k - 1).query_dis <= mini_border) {
            cars = cars.subList(0, k);
            System.out.println("初始运算");
        } else {
            System.out.println("测试运算");

            if (!All_Vertex.get(query_name).isactive) {//判断查询点是否是活跃点
                grids[i][j].addQuery(query_name);//如果不是活跃点，则连接查询点边
            }
            grids[i][j].init_query_dvalue(query_name);
            grids[i][j].set_init_neighbor(current_names);
            this.query_name = query_name;
            x = i;
            y = j;
            run();

        }

        display();
    }

    private void display() {
        System.out.println("添加汽车时间=" + sum_car + "毫秒");
        for (int i = 0; i < cars.size(); i++) {
            System.out.println("the Car name=" + cars.get(i).name + "      query_dis=" + cars.get(i).query_dis);
        }
    }

    private void run() {
        expend();
        long s = System.nanoTime()/1000;
        while (true) {
            if (Dijkstra()) {
                break;
            }
            expend();
        }
        long l = System.nanoTime()/1000;
        System.out.println("run查询时间=" + (l - s) + "微秒");
        sumtime=sumtime+l-s;
        System.out.println("mini_border=" + mini_border);
    }

    //拓展范围
        private void expend() {

        long ss = System.currentTimeMillis();
        mini_border = Double.MAX_VALUE;
        level++;
        m = (x - level) * width;
        n = (x + level + 1) * width;
        p = (y - level) * width;
        q = (y + level + 1) * width;
        int xmin = x - level >= 0 ? x - level : 0, xmax = x + level < row ? x + level : row - 1, ymin = y - level >= 0 ? y - level : 0, ymax = y + level < column ? y + level : column - 1;

        for (int i = xmin; i <= xmax; i++) {
            grids[i][ymin].set_neighbor(current_names);
            grids[i][ymax].set_neighbor(current_names);
        }
        for (int i = ymin + 1; i <= ymax - 1; i++) {
            grids[xmin][i].set_neighbor(current_names);
            grids[xmax][i].set_neighbor(current_names);
        }

        long ll = System.currentTimeMillis();
        System.out.println("拓展层数=" + level + ";    拓展时间=" + (ll - ss) + "毫秒");
    }

    private boolean Dijkstra() {
        boolean gnav = false;//判断当前范围内的k辆车，是不是当前范围内最近的k辆车
        while (!current_names.isEmpty()) {
            min_value = Double.MAX_VALUE;
            for (Integer i : current_names) {
                if (dvalue[i] < min_value && dvalue[i] != -1) {
                    min_pos = i;
                    min_value = dvalue[i];
                }
            }
            if (min_value == Double.MAX_VALUE) {//剩下的点都与查询点没有道路相通
                break;
            }
            Vertex vx = All_Vertex.get(min_pos);
            if ((vx.x == p || vx.x == q || vx.y == m || vx.y == n) && mini_border > min_value) {//更新最近边界点距离
                mini_border = min_value;
            }
            if (!gnav) {
                gnav = add_car(vx);
            }
            current_names.remove(min_pos);
            remove_names.add(min_pos);
            HashSet<Vnode> nei = vx.neighbors;
            for (Vnode v : nei) {
                relax(min_pos, v.name, v.distence);
            }
        }
        if (k_now == k && max_car <= mini_border) {
            return true;
        }
        return false;

    }

    private boolean add_car(Vertex v) {
        boolean flag = false;//flag=true，说明这个点曾经加到过kcar中去
        if (k_now < k) {//当前拥有的车少于k

            if (v.isactive) {//如果是活跃点
                if (cars.contains(v.cars.get(0))) {
                    flag = true;
                }

                int size = v.cars.size();
                if (k_now + size < k) {
                    if (!flag) {
                        cars.addAll(v.cars);
                    }
                    for (Car c : v.cars) {
                        c.query_dis = c.dis + min_pos;
                    }
                    k_now += size;
                } else if (flag) {//如果车已经在kcar中了，则改变query_dis
                    for (Car c : v.cars) {
                        c.query_dis = min_value + c.dis;
                    }
                } else {
                    for (Car c : v.cars.subList(0, k - k_now)) {
                        c.query_dis = min_value + c.dis;
                        cars.add(c);
                    }
                    k_now = k;
                    Collections.sort(cars, new CostComprator());//对cars进行排序
                    max_car = cars.get(k - 1).query_dis;
                }
            }
            return false;
        } else if (min_value >= max_car) {//当前范围内这k辆车已经是最近的k辆车了
            return true;
        } else if (v.isactive) {
            for (Car c : v.cars) {
                c.query_dis = c.dis + min_value;
                if (!cars.contains(c) && c.query_dis < max_car) {
                    cars.set(k - 1, c);
                }
                Collections.sort(cars, new CostComprator());//对cars进行排序
                max_car = cars.get(k - 1).query_dis;
            }
        }
        return false;
    }

    private void relax(Integer u, Integer v, double dis) {
        if (dvalue[v] == -1 || dvalue[v] > dvalue[u] + dis) {
            dvalue[v] = dvalue[u] + dis;
            if (remove_names.contains(v)) {
                remove_names.remove(v);
                current_names.add(v);

            }
        }
    }

    static class CostComprator implements Comparator {

        public int compare(Object object1, Object object2) {// 实现接口中的方法  
            Car p1 = (Car) object1; // 强制转换  
            Car p2 = (Car) object2;
            return Double.compare(p1.query_dis, p2.query_dis);
        }
    }

}
